package day0402

import (
	"sort"
)

func findUnsortedSubarray1(nums []int) int {
	if sort.IntsAreSorted(nums) {
		return 0
	}
	n := len(nums)
	sortedNums := make([]int, n)
	copy(sortedNums, nums)
	sort.Ints(sortedNums)

	left, right := 0, n-1
	for nums[left] == sortedNums[left] {
		left++
	}
	for nums[right] == sortedNums[right] {
		right--
	}
	return right - left + 1
}

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	left, right := 0, -1
	max := nums[0]
	min := nums[n-1]
	for i := 0; i < n; i++ {
		if nums[i] >= max {
			max = nums[i]
		} else {
			right = i
		}
	}

	for i := n - 1; i >= 0; i-- {
		if nums[i] <= min {
			min = nums[i]
		} else {
			left = i
		}
	}
	return right - left + 1
}
